{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from  optimization import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##本duan代码要写入optimization.py\n",
    "people = [('Seymour','BOS'),\n",
    "          ('Franny','DAL'),\n",
    "          ('Zooey','CAK'),\n",
    "          ('Walt','MIA'),\n",
    "          ('Buddy','ORD'),\n",
    "          ('Les','OMA')]\n",
    "# Laguardia\n",
    "destination='LGA'\n",
    "\n",
    "flights={}\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "for line in file('schedule.txt'):\n",
    "    origin,dest,depart,arrive,price=line.strip().split(',')\n",
    "    flights.setdefault((origin,dest),[])\n",
    "\n",
    "  # Add details to the list of possible flights\n",
    "    flights[(origin,dest)].append((depart,arrive,int(price)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('LGA', 'OMA'): [('6:19', '8:13', 239),\n",
       "  ('8:04', '10:59', 136),\n",
       "  ('9:31', '11:43', 210),\n",
       "  ('11:07', '13:24', 171),\n",
       "  ('12:31', '14:02', 234),\n",
       "  ('14:05', '15:47', 226),\n",
       "  ('15:07', '17:21', 129),\n",
       "  ('16:35', '18:56', 144),\n",
       "  ('18:25', '20:34', 205),\n",
       "  ('20:05', '21:44', 172)],\n",
       " ('OMA', 'LGA'): [('6:11', '8:31', 249),\n",
       "  ('7:39', '10:24', 219),\n",
       "  ('9:15', '12:03', 99),\n",
       "  ('11:08', '13:07', 175),\n",
       "  ('12:18', '14:56', 172),\n",
       "  ('13:37', '15:08', 250),\n",
       "  ('15:03', '16:42', 135),\n",
       "  ('16:51', '19:09', 147),\n",
       "  ('18:12', '20:17', 242),\n",
       "  ('20:05', '22:06', 261)],\n",
       " ('LGA', 'ORD'): [('6:03', '8:43', 219),\n",
       "  ('7:50', '10:08', 164),\n",
       "  ('9:11', '10:42', 172),\n",
       "  ('10:33', '13:11', 132),\n",
       "  ('12:08', '14:47', 231),\n",
       "  ('14:19', '17:09', 190),\n",
       "  ('15:04', '17:23', 189),\n",
       "  ('17:06', '20:00', 95),\n",
       "  ('18:33', '20:22', 143),\n",
       "  ('19:32', '21:25', 160)],\n",
       " ('ORD', 'LGA'): [('6:05', '8:32', 174),\n",
       "  ('8:25', '10:34', 157),\n",
       "  ('9:42', '11:32', 169),\n",
       "  ('11:01', '12:39', 260),\n",
       "  ('12:44', '14:17', 134),\n",
       "  ('14:22', '16:32', 126),\n",
       "  ('15:58', '18:40', 173),\n",
       "  ('16:43', '19:00', 246),\n",
       "  ('18:48', '21:45', 246),\n",
       "  ('19:50', '22:24', 269)],\n",
       " ('LGA', 'MIA'): [('6:33', '9:14', 172),\n",
       "  ('8:23', '11:07', 143),\n",
       "  ('9:25', '12:46', 295),\n",
       "  ('11:08', '14:38', 262),\n",
       "  ('12:37', '15:05', 170),\n",
       "  ('14:08', '16:09', 232),\n",
       "  ('15:23', '18:49', 150),\n",
       "  ('16:50', '19:26', 304),\n",
       "  ('18:07', '21:30', 355),\n",
       "  ('20:27', '23:42', 169)],\n",
       " ('MIA', 'LGA'): [('6:25', '9:30', 335),\n",
       "  ('7:34', '9:40', 324),\n",
       "  ('9:15', '12:29', 225),\n",
       "  ('11:28', '14:40', 248),\n",
       "  ('12:05', '15:30', 330),\n",
       "  ('14:01', '17:24', 338),\n",
       "  ('15:34', '18:11', 326),\n",
       "  ('17:07', '20:04', 291),\n",
       "  ('18:23', '21:35', 134),\n",
       "  ('19:53', '22:21', 173)],\n",
       " ('LGA', 'BOS'): [('6:39', '8:09', 86),\n",
       "  ('8:23', '10:28', 149),\n",
       "  ('9:58', '11:18', 130),\n",
       "  ('10:33', '12:03', 74),\n",
       "  ('12:08', '14:05', 142),\n",
       "  ('13:39', '15:30', 74),\n",
       "  ('15:25', '16:58', 62),\n",
       "  ('17:03', '18:03', 103),\n",
       "  ('18:24', '20:49', 124),\n",
       "  ('19:58', '21:23', 142)],\n",
       " ('BOS', 'LGA'): [('6:17', '8:26', 89),\n",
       "  ('8:04', '10:11', 95),\n",
       "  ('9:45', '11:50', 172),\n",
       "  ('11:16', '13:29', 83),\n",
       "  ('12:34', '15:02', 109),\n",
       "  ('13:40', '15:37', 138),\n",
       "  ('15:27', '17:18', 151),\n",
       "  ('17:11', '18:30', 108),\n",
       "  ('18:34', '19:36', 136),\n",
       "  ('20:17', '22:22', 102)],\n",
       " ('LGA', 'DAL'): [('6:09', '9:49', 414),\n",
       "  ('7:57', '11:15', 347),\n",
       "  ('9:49', '13:51', 229),\n",
       "  ('10:51', '14:16', 256),\n",
       "  ('12:20', '16:34', 500),\n",
       "  ('14:20', '17:32', 332),\n",
       "  ('15:49', '20:10', 497),\n",
       "  ('17:14', '20:59', 277),\n",
       "  ('18:44', '22:42', 351),\n",
       "  ('19:57', '23:15', 512)],\n",
       " ('DAL', 'LGA'): [('6:12', '10:22', 230),\n",
       "  ('7:53', '11:37', 433),\n",
       "  ('9:08', '12:12', 364),\n",
       "  ('10:30', '14:57', 290),\n",
       "  ('12:19', '15:25', 342),\n",
       "  ('13:54', '18:02', 294),\n",
       "  ('15:44', '18:55', 382),\n",
       "  ('16:52', '20:48', 448),\n",
       "  ('18:26', '21:29', 464),\n",
       "  ('20:07', '23:27', 473)],\n",
       " ('LGA', 'CAK'): [('6:58', '9:01', 238),\n",
       "  ('8:19', '11:16', 122),\n",
       "  ('9:58', '12:56', 249),\n",
       "  ('10:32', '13:16', 139),\n",
       "  ('12:01', '13:41', 267),\n",
       "  ('13:37', '15:33', 142),\n",
       "  ('15:50', '18:45', 243),\n",
       "  ('16:33', '18:15', 253),\n",
       "  ('18:17', '21:04', 259),\n",
       "  ('19:46', '21:45', 214)],\n",
       " ('CAK', 'LGA'): [('6:08', '8:06', 224),\n",
       "  ('8:27', '10:45', 139),\n",
       "  ('9:15', '12:14', 247),\n",
       "  ('10:53', '13:36', 189),\n",
       "  ('12:08', '14:59', 149),\n",
       "  ('13:40', '15:38', 137),\n",
       "  ('15:23', '17:25', 232),\n",
       "  ('17:08', '19:08', 262),\n",
       "  ('18:35', '20:28', 204),\n",
       "  ('20:30', '23:11', 114)]}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "flights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   Seymour       BOS  8:04-10:11 $ 95 12:08-14:05 $142\n",
      "    Franny       DAL 12:19-15:25 $342 10:51-14:16 $256\n",
      "     Zooey       CAK 10:53-13:36 $189  9:58-12:56 $249\n",
      "      Walt       MIA  9:15-12:29 $225 16:50-19:26 $304\n",
      "     Buddy       ORD 16:43-19:00 $246 10:33-13:11 $132\n",
      "       Les       OMA 11:08-13:07 $175 15:07-17:21 $129\n"
     ]
    }
   ],
   "source": [
    "s=[1,4,3,2,7,3,6,3,2,4,5,3]\n",
    "printschedule(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5235"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedulecost(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "domain=[(0,9)]*(len(people)*2)\n",
    "#domain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6.0, 5.0, 8.0, 7.0, 3.0, 7.0, 0.0, 8.0, 0.0, 7.0, 3.0, 6.0]\n",
      "6264\n",
      "   Seymour       BOS 15:27-17:18 $151 13:39-15:30 $ 74\n",
      "    Franny       DAL 13:54-18:02 $294 18:44-22:42 $351\n",
      "     Zooey       CAK 18:35-20:28 $204 16:33-18:15 $253\n",
      "      Walt       MIA 17:07-20:04 $291 11:08-14:38 $262\n",
      "     Buddy       ORD 11:01-12:39 $260 17:06-20:00 $ 95\n",
      "       Les       OMA 16:51-19:09 $147  6:19- 8:13 $239\n",
      "[3.0, 7.0, 2.0, 7.0, 9.0, 6.0, 3.0, 8.0, 3.0, 6.0, 6.0, 6.0]\n",
      "6179\n",
      "   Seymour       BOS 11:16-13:29 $ 83 17:03-18:03 $103\n",
      "    Franny       DAL 16:52-20:48 $448  9:49-13:51 $229\n",
      "     Zooey       CAK  9:15-12:14 $247 16:33-18:15 $253\n",
      "      Walt       MIA 17:07-20:04 $291 20:27-23:42 $169\n",
      "     Buddy       ORD 19:50-22:24 $269 15:04-17:23 $189\n",
      "       Les       OMA 15:03-16:42 $135 11:07-13:24 $171\n",
      "[6.0, 6.0, 3.0, 5.0, 3.0, 6.0, 3.0, 4.0, 4.0, 1.0, 3.0, 5.0]\n",
      "4279\n",
      "   Seymour       BOS 15:27-17:18 $151 15:25-16:58 $ 62\n",
      "    Franny       DAL 15:44-18:55 $382 10:51-14:16 $256\n",
      "     Zooey       CAK 10:53-13:36 $189 13:37-15:33 $142\n",
      "      Walt       MIA 14:01-17:24 $338 11:08-14:38 $262\n",
      "     Buddy       ORD 11:01-12:39 $260 15:04-17:23 $189\n",
      "       Les       OMA 15:03-16:42 $135 11:07-13:24 $171\n",
      "[0.0, 0.0, 7.0, 6.0, 9.0, 8.0, 3.0, 1.0, 1.0, 8.0, 9.0, 2.0]\n",
      "7639\n",
      "   Seymour       BOS  6:17- 8:26 $ 89  6:39- 8:09 $ 86\n",
      "    Franny       DAL  6:12-10:22 $230 17:14-20:59 $277\n",
      "     Zooey       CAK 17:08-19:08 $262 15:50-18:45 $243\n",
      "      Walt       MIA 15:34-18:11 $326 20:27-23:42 $169\n",
      "     Buddy       ORD 19:50-22:24 $269 18:33-20:22 $143\n",
      "       Les       OMA 18:12-20:17 $242 11:07-13:24 $171\n",
      "[6.0, 0.0, 3.0, 9.0, 5.0, 6.0, 0.0, 5.0, 3.0, 0.0, 5.0, 1.0]\n",
      "6548\n",
      "   Seymour       BOS 15:27-17:18 $151  6:39- 8:09 $ 86\n",
      "    Franny       DAL  6:12-10:22 $230 10:51-14:16 $256\n",
      "     Zooey       CAK 10:53-13:36 $189 19:46-21:45 $214\n",
      "      Walt       MIA 19:53-22:21 $173 14:08-16:09 $232\n",
      "     Buddy       ORD 14:22-16:32 $126 15:04-17:23 $189\n",
      "       Les       OMA 15:03-16:42 $135  6:19- 8:13 $239\n",
      "[2.0, 6.0, 5.0, 7.0, 2.0, 5.0, 0.0, 5.0, 2.0, 5.0, 5.0, 3.0]\n",
      "6716\n",
      "   Seymour       BOS  9:45-11:50 $172 15:25-16:58 $ 62\n",
      "    Franny       DAL 15:44-18:55 $382 14:20-17:32 $332\n",
      "     Zooey       CAK 13:40-15:38 $137 16:33-18:15 $253\n",
      "      Walt       MIA 17:07-20:04 $291  9:25-12:46 $295\n",
      "     Buddy       ORD  9:42-11:32 $169 14:19-17:09 $190\n",
      "       Les       OMA 13:37-15:08 $250  6:19- 8:13 $239\n",
      "[7.0, 6.0, 9.0, 9.0, 1.0, 9.0, 6.0, 8.0, 3.0, 8.0, 8.0, 0.0]\n",
      "6696\n",
      "   Seymour       BOS 17:11-18:30 $108 15:25-16:58 $ 62\n",
      "    Franny       DAL 15:44-18:55 $382 19:57-23:15 $512\n",
      "     Zooey       CAK 20:30-23:11 $114 19:46-21:45 $214\n",
      "      Walt       MIA 19:53-22:21 $173  8:23-11:07 $143\n",
      "     Buddy       ORD  8:25-10:34 $157 19:32-21:25 $160\n",
      "       Les       OMA 20:05-22:06 $261 15:07-17:21 $129\n",
      "[2.0, 2.0, 1.0, 4.0, 0.0, 6.0, 2.0, 7.0, 0.0, 6.0, 7.0, 8.0]\n",
      "5416\n",
      "   Seymour       BOS  9:45-11:50 $172  9:58-11:18 $130\n",
      "    Franny       DAL  9:08-12:12 $364  7:57-11:15 $347\n",
      "     Zooey       CAK  8:27-10:45 $139 12:01-13:41 $267\n",
      "      Walt       MIA 12:05-15:30 $330  6:33- 9:14 $172\n",
      "     Buddy       ORD  6:05- 8:32 $174 15:04-17:23 $189\n",
      "       Les       OMA 15:03-16:42 $135  9:31-11:43 $210\n",
      "[4.0, 4.0, 8.0, 4.0, 6.0, 5.0, 4.0, 9.0, 6.0, 4.0, 9.0, 0.0]\n",
      "4877\n",
      "   Seymour       BOS 12:34-15:02 $109 12:08-14:05 $142\n",
      "    Franny       DAL 12:19-15:25 $342 18:44-22:42 $351\n",
      "     Zooey       CAK 18:35-20:28 $204 12:01-13:41 $267\n",
      "      Walt       MIA 12:05-15:30 $330 15:23-18:49 $150\n",
      "     Buddy       ORD 15:58-18:40 $173 14:19-17:09 $190\n",
      "       Les       OMA 13:37-15:08 $250 12:31-14:02 $234\n",
      "[6.0, 5.0, 2.0, 4.0, 6.0, 9.0, 9.0, 5.0, 5.0, 8.0, 5.0, 2.0]\n",
      "6129\n",
      "   Seymour       BOS 15:27-17:18 $151 13:39-15:30 $ 74\n",
      "    Franny       DAL 13:54-18:02 $294  9:49-13:51 $229\n",
      "     Zooey       CAK  9:15-12:14 $247 12:01-13:41 $267\n",
      "      Walt       MIA 12:05-15:30 $330 15:23-18:49 $150\n",
      "     Buddy       ORD 15:58-18:40 $173 19:32-21:25 $160\n",
      "       Les       OMA 20:05-22:06 $261 20:05-21:44 $172\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    s=randomoptimize(domain,schedulecost)\n",
    "    print(s)\n",
    "\n",
    "    print (schedulecost(s))\n",
    "    printschedule(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 3, 3, 5, 5, 0, 3, 1, 7, 1, 7, 8]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol=[random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]\n",
    "sol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(domain)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3764\n",
      "   Seymour       BOS 12:34-15:02 $109 10:33-12:03 $ 74\n",
      "    Franny       DAL 10:30-14:57 $290  7:57-11:15 $347\n",
      "     Zooey       CAK  8:27-10:45 $139 10:32-13:16 $139\n",
      "      Walt       MIA 11:28-14:40 $248  6:33- 9:14 $172\n",
      "     Buddy       ORD  6:05- 8:32 $174  9:11-10:42 $172\n",
      "       Les       OMA  9:15-12:03 $ 99  8:04-10:59 $136\n"
     ]
    }
   ],
   "source": [
    "s=hillclimb(domain,schedulecost)\n",
    "print(schedulecost(s))\n",
    "printschedule(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4787\n",
      "   Seymour       BOS 18:34-19:36 $136 15:25-16:58 $ 62\n",
      "    Franny       DAL 15:44-18:55 $382 10:51-14:16 $256\n",
      "     Zooey       CAK 10:53-13:36 $189 13:37-15:33 $142\n",
      "      Walt       MIA 14:01-17:24 $338  8:23-11:07 $143\n",
      "     Buddy       ORD  8:25-10:34 $157 17:06-20:00 $ 95\n",
      "       Les       OMA 16:51-19:09 $147  8:04-10:59 $136\n"
     ]
    }
   ],
   "source": [
    "\n",
    "s=annealingoptimize(domain,schedulecost)\n",
    "\n",
    "print(schedulecost(s))\n",
    "printschedule(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3759\n",
      "3759\n",
      "   Seymour       BOS  8:04-10:11 $ 95  6:39- 8:09 $ 86\n",
      "    Franny       DAL  6:12-10:22 $230  9:49-13:51 $229\n",
      "     Zooey       CAK  9:15-12:14 $247  9:58-12:56 $249\n",
      "      Walt       MIA  9:15-12:29 $225 11:08-14:38 $262\n",
      "     Buddy       ORD 11:01-12:39 $260  9:11-10:42 $172\n",
      "       Les       OMA  9:15-12:03 $ 99 11:07-13:24 $171\n"
     ]
    }
   ],
   "source": [
    "\n",
    "s=geneticoptimize(domain,schedulecost,step=1,popsize=100,elite=0.05,mutprob=0.05)\n",
    "\n",
    "print(schedulecost(s))\n",
    "printschedule(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
